package algorithm.poj.p2000;


public class P2719TLE {

	/**
	 * @param args
	 */
	public static void main(String[] args)
	throws Exception {

//		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
//
//        String line;
//        String s = "";
//
//        line = stdin.readLine().trim();
//        while (!"0".equals(line)) {
//        	int n = Integer.valueOf(line);
//            s += n + ": " + get(n) + "\n";
//            line = stdin.readLine().trim();
//        }
//		System.out.println(s);
		
		long t = System.currentTimeMillis();
		for (int i = 0; i < 1000000; i ++) {
			shrink(999999999);
		}
		System.out.println((System.currentTimeMillis()-t) + " ms");
		t = System.currentTimeMillis();
		for (int i = 0; i < 1000000; i ++) {
			get(999999999);
		}
		System.out.println((System.currentTimeMillis()-t) + " ms");
	}
	
	static long[] pow10 = {
			1, 		10, 	100, 	1000, 	10000,		100000,
			1000000,		10000000,		100000000, 		
			1000000000, 	10000000000L
	};
	
	static long[] pow9 = {
		1, 		9, 		81, 		729, 	6561,		59049,
		531441,			4782969,	43046721, 			387420489, 	
		3486784401L
	};
	
	static long[][] dpow;
	static {
		dpow = new long[10][];
		for (int i = 0; i < 10; i ++) {
			dpow[i] = new long[pow10.length];
			for (int j = 0; j < pow10.length; j ++) {
				dpow[i][j] = i*getD(j);
			}
		}
	}

	public static long get(long n) {
		
		return n-getN(n);
	}

	/**
	 * ������返回不超过d位的数字中，含4的数的数目。
	 * 换言之，就是0～9...9(d个9)中含4的数字的个数
	 * @param d
	 * @return
	 */
	public static long getD(int d) {
		return pow10[d]-pow9[d];
	}
	
	/**
	 * 返回不超过(t0...0)(d个0)的数中，含4的数的数目。
	 * @param t
	 * @param d
	 * @return
	 */
	public static long getT(int t, int d) {
		if (t < 4) {
			return dpow[t][d];
		} else if (t == 4) {
			return dpow[t][d]+1; 
		} else {
			return dpow[t-1][d]+pow10[d];
		}
	}
	
	/**
	 * 返回不超过n的数中，含4的数的数目。
	 * 
	 * @param n
	 * @return
	 */
	public static long getN(long n) {
		long m = 0;
		int c = 0;
		while (n > 0) {
			m += getT((int)n%10, c);
			c ++;
			n /= 10;
		}
		return m;
	}

	public static int shrink(int i) {
	    int s = 0;
	    for (int d = 0; i > 0; d++) {
	        int j = i % 10;
	        if (j > 4) j--;
	        s += j * pow9[d];
	        i /= 10;
	    }
	    return s;
	}
}
